class Solution {
public:
    int searchInsert(vector<int>& nums, int target)
    {
        //二分查找，给的是一个排序数列
        int begin=0,end=nums.size()-1;//头尾
        int ret=0,count=0;
        while(begin<end)
        {
            int middle=(begin+end)/2;//中间值

            if(middle==begin||middle==end)//1找不到，2可能在这里面
            {
                //俩已经相邻了
                count++;
                if(count==2)
                {
                    break;
                }
            }
            if(nums[middle]>target)
            {
                end=middle;
            }
            else if(nums[middle]<target)
            {
                begin=middle;
            }
            else
            {
                //找到或找不到都是middle这个位置
                 return middle;
            }

        }


        //找不到的情况
        //begin ,end 的值,....遍历
        if(abs(begin-end)==1)
        {
            for(int i =begin;i<=end;i++)
            {
                if(target<nums[i]||target==nums[i]) {
                    return i;
                }

             }
        }
         if(nums[end]<target)
            {
                return end+1;
             }
        return 0;
    }
};
